package com.wanma;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

public class LeetCode967 {

	public ArrayList<String> strList = new ArrayList<String>();
	public String string = new String();
	public int[] numsSameConsecDiff(int N, int K) {
		if(N == 1){				//N为1，直接返回答案
			int[] res = {0,1,2,3,4,5,6,7,8,9};
			return res;
		}		
	    for(int i = 1;i <= 9;i++){//N大于1的情况
	    	string = new String();	//用字符串存储可行的结果，也可以直接用数字
	    	string += i;
	    	hasChar(string, string.charAt(0), N, K);
	    }
	    int[] res = new int[strList.size()];
	    for(int i = 0; i < res.length;i++)
	    	res[i] = Integer.valueOf(strList.get(i));
		return res;
	}
	public void hasChar(String str,char ch,int N,int K){
		if((char)(ch - '0') - K >= 0){		//判断是否有符合要求的字符
			char newChar = (char)(ch - K);
			str += newChar;					//将新字符添加到字符串
			if(str.length() < N){
				hasChar(str, newChar, N, K);
			}else if(str.length() == N && !strList.contains(str)){
				strList.add(str);		
			}	
			str = str.substring(0,str.length() -1);//将上一步已经添加的新字符删除
		}
		if((char)(ch - '0') + K <= 9){		//新字符大于原字符的情况
			char newChar = (char)(ch + K);
			str += newChar;
			if(str.length() < N){
				hasChar(str, newChar, N, K);
			}else if(str.length() == N && !strList.contains(str)){
				strList.add(str);			
			}
			str = str.substring(0,str.length() -1);
		}					
	}
	
	
}
class Solution {
    public int[] numsSameConsecDiff(int N, int K) {
        Set<Integer> cur = new HashSet();
        for (int i = 1; i <= 9; ++i)
            cur.add(i);

        for (int steps = 1; steps <= N-1; ++steps) {
            Set<Integer> cur2 = new HashSet();
            for (int x: cur) {
                int d = x % 10;
                if (d-K >= 0)
                    cur2.add(10*x + (d-K));
                if (d+K <= 9)
                    cur2.add(10*x + (d+K));
            }

            cur = cur2;
        }

        if (N == 1)
            cur.add(0);

        int[] ans = new int[cur.size()];
        int t = 0;
        for (int x: cur)
            ans[t++] = x;
        return ans;
    }
}